package com.hanxiaozhang.bitoperation;

/**
 * 〈一句话功能简述〉<br>
 * 〈异或运算〉
 *
 * @author hanxinghua
 * @create 2021/9/4
 * @since 1.0.0
 */
public class Xor {


    /*
     * 位运算:
     * 位运算符包含:　与（&）、非（~）、或（|）、异或（^）
     *
     * &：当两边操作数的位两边都为1时，结果为1，否则为0。如1100&1010=1000
     * |：当两边操作数的位有一边为1时，结果为1。否则为0。如1100|1010=1110
     * ~：0变1,1变0
     * ^：两边的位不同一时,结果为1。否则为0.如1100^1010=0110
     *
     * << 表示带符号左移，左移一位表示原来的值乘2，左移时不管正负，低位补0。
     * >> 表示带符号右移，右移一位表示原来的值除2，正数右移高位补0，负数右移高位补1
     * >>> 表示无符号右移（逻辑右移），若该数为正数，则高位补0，若该数为负数，则同样高位补0
     *
     */


    public static void main(String[] args) {

//        topic1(3, 4);
//
//        int[] arr = {1, 2, 1, 2, 4, 3, 4};
//        topic2(arr);
//
//        topic3(101);
//
//        int[] arr_1 = {1, 2, 1, 2, 4, 3, 4, 8, 4, 4};
//        topic4(arr_1);

        topic5(101);

    }


    int a = 6, b = 7;

    /**
     * 如何不用额外变量的情况下交互两个数（前提是两个数不指向同一个内存地址）：
     *
     * @param a
     * @param b
     * @return
     */
    public static void topic1(int a, int b) {
        System.out.println("swap before: a is " + a + " b is " + b);
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
        System.out.println("swap after: a is " + a + " b is " + b);
    }

    /**
     * 一个数组中只有一种出现了奇数次，其他数都出现了偶数次，怎么找到奇数此数，并打印这种数
     *
     * @param arr
     * @return
     */
    public static int topic2(int[] arr) {
        int target = 0;
        for (int i = 0; i < arr.length; i++) {
            target = target ^ arr[i];
        }
        System.out.println("target is " + target);
        return target;
    }

    /**
     * 怎么把一个int类型的数，在二进制的情形下，提取出最右侧的1来
     *
     * @param num
     * @return
     */
    public static int topic3(int num) {

        System.out.println("num binary is ：" + Integer.toBinaryString(num));
        int target = num & ((~num) + 1);
        System.out.println("target binary is ：" + Integer.toBinaryString(target));
        return target;
    }

    /**
     * 一个数组中只有两种出现了奇数次，其他数都出现了偶数次，怎么找到两种奇数次，并打印这种数：
     * 设两种奇数次，分别为 x ，y
     *
     * @param arr
     * @return
     */
    public static void topic4(int[] arr) {
        int target = 0;
        for (int i = 0; i < arr.length; i++) {
            target = target ^ arr[i];
        }
        // 以上操作得到：target = x ^ y ，并且 target  = x ^ y != 0
        // 提取出最右侧的1
        int rightOne = target & ((~target) + 1);
        int onlyOne = 0;

        for (int i = 0; i < arr.length; i++) {
            // 分组：x ^ y 与最右侧为1的一组，x ^ y与最右侧不为1的一组
            // 假设：arr[1]  =  111100011110000
            //	 rightOne   =  000000000010000
            //   同一组：       000000000010000
            if ((arr[i] & rightOne) == rightOne) {
                onlyOne = onlyOne ^ arr[i];
            }
        }
        System.out.println("x is " + onlyOne + " y is " + (target ^ onlyOne));

    }

    /**
     * 给出一个数，数二进制含有1的个数：
     * 用到N & ((~N) + 1) 提取出最右侧的1知识
     *
     * @param num
     * @return
     */
    public static void topic5(int num) {

        System.out.println("num binary is ：" + Integer.toBinaryString(num));
        int count = 0;
        while (num != 0) {
            int target = num & ((~num) + 1);
            count++;
            num ^= target;
        }
        System.out.println("num count 1 is ：" + count);
    }


}
